Longest repeating substring [Rabin-Karp Algorithm]

Time: O(NLogN); Space: O(N); medium

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

Example 1:

Input: S = “abcd”

Output: 0

Explanation:

  • There is no repeating substring.

Example 2:

Input: S = “abbaba”

Output: 2

Explanation:

  • The longest repeating substrings are “ab” and “ba”, each of which occurs twice.

Example 3:

Input: S = “aabcaabdaab”

Output: 3

Explanation:

  • The longest repeating substring is “aab”, which occurs 3 times.

Example 4:

Input: S = “aaaaa”

Output: 4

Explanation:

  • The longest repeating substring is “aaaa”, which occurs twice.

Constraints:

  • The string S consists of only lowercase English letters from ‘a’ - ‘z’.

  • 1 <= len(S) <= 1500

1. Binary Search [O(NLogN), O(N)]

[3]:

import collections
import functools

class Solution1(object):
    """
    Time: O(NLogN), N = len(S)
    Space: O(N)
    """
    def longestRepeatingSubstring(self, S):
        """
        :type S: str
        :rtype: int
        """
        M = 10**9+7
        D = 26

        def check(S, L):
            p = pow(D, L, M)
            curr = functools.reduce(lambda x, y: (D*x+ord(y)-ord('a')) % M, S[:L], 0)
            lookup = collections.defaultdict(list)
            lookup[curr].append(L-1)
            result = 0

            for i in range(L, len(S)):

                curr = ((D*curr) % M + ord(S[i])-ord('a') -
                        ((ord(S[i-L])-ord('a'))*p) % M) % M

                if curr in lookup:
                    for j in lookup[curr]:
                        if S[j-L+1:j+1] == S[i-L+1:i+1]:
                            if result == 0:
                                result = i
                            return result-L+1
                lookup[curr].append(i)
            return result

        left, right = 0, len(S)-1

        while left <= right:
            mid = left + (right-left) // 2
            if not check(S, mid):
                right = mid - 1
            else:
                left = mid + 1

        return right

[4]:

s = Solution1()

S = "abcd"
assert s.longestRepeatingSubstring(S) == 0

S = "abbaba"
assert s.longestRepeatingSubstring(S) == 2

S = "aabcaabdaab"
assert s.longestRepeatingSubstring(S) == 3

S = "aaaaa"
assert s.longestRepeatingSubstring(S) == 4